//
//  ViewController.m
//  Algorithm
//
//  Created by zxs on 2017/6/6.
//  Copyright © 2017年 zxs. All rights reserved.
//

#import "ViewController.h"

@interface ViewController ()
@property (weak, nonatomic) IBOutlet UITextView *logTextView;

@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view, typically from a nib.
}


- (void)didReceiveMemoryWarning {
    [super didReceiveMemoryWarning];
    // Dispose of any resources that can be recreated.
}

#pragma mark - action
- (IBAction)clearButtonTouched:(UIButton *)sender {
    self.logTextView.text = @"";
}

- (IBAction)factorialButtonTouched:(UIButton *)sender {
    [self appendLog:@"10的阶乘："];
    [self appendLog:[NSString stringWithFormat:@"%d", factorial(10)]];
}

- (IBAction)gcdButtonTouched:(UIButton *)sender {
    [self appendLog:@"50和32的最大公约数："];
    [self appendLog:[NSString stringWithFormat:@"%d", gcd(32, 50)]];
}

- (IBAction)quickSortButtonTouched:(UIButton *)sender {
    [self appendLog:@"排序前的数组："];
    int numArr[10] = {86, 37, 56, 29, 92, 73, 15, 63, 30, 8};
    for (int i = 0; i < 10; i++) {
        [self appendLog:[NSString stringWithFormat:@"%d,", numArr[i]] withLine:NO];
    }
    [self appendLog:@"\n"];
    quick_sort(numArr, 0, 9);
    [self appendLog:@"排序后的数组："];
    for (int i = 0; i < 10; i++) {
        [self appendLog:[NSString stringWithFormat:@"%d,", numArr[i]] withLine:NO];
    }
    [self appendLog:@"\n"];
}

- (IBAction)bubbleButtonTouched:(UIButton *)sender {
    [self appendLog:@"排序前的数组："];
    int numArr[10] = {86, 37, 56, 29, 92, 73, 15, 63, 30, 8};
    for (int i = 0; i < 10; i++) {
        [self appendLog:[NSString stringWithFormat:@"%d,", numArr[i]] withLine:NO];
    }
    [self appendLog:@"\n"];
    bubble_sort(numArr, 10);
    [self appendLog:@"排序后的数组："];
    for (int i = 0; i < 10; i++) {
        [self appendLog:[NSString stringWithFormat:@"%d,", numArr[i]] withLine:NO];
    }
    [self appendLog:@"\n"];
}

- (IBAction)binarySearchButtonTouched:(UIButton *)sender {
    [self appendLog:@"查询的数组："];
    int numArr[10] = {8, 15, 29, 30, 37, 56, 63, 73, 86, 92};
    for (int i = 0; i < 10; i++) {
        [self appendLog:[NSString stringWithFormat:@"%d,", numArr[i]] withLine:NO];
    }
    [self appendLog:@"\n"];
    [self appendLog:@"查询的数值：86"];
    int index = binary_search(numArr, 10, 86);
    [self appendLog:[NSString stringWithFormat:@"查询到的下标为：%d", index]];
}

- (IBAction)primeButtonTouched:(UIButton *)sender {
    [self appendLog:@"100以内的质数："];
    for (int i = 3; i < 100; i++) {
        if (1 == isPrime(i)) {
            [self appendLog:[NSString stringWithFormat:@"%d,", i] withLine:NO];
        }
    }
}

- (IBAction)reverseButtonTouched:(UIButton *)sender {
    char s[] = "hello world";
    [self appendLog:@"原始顺序的字符串："];
    [self appendLog:[NSString stringWithUTF8String:s]];
    reverse(s);
    [self appendLog:@"逆序的字符串："];
    [self appendLog:[NSString stringWithUTF8String:s]];
}

# pragma mark - private
- (void)appendLog: (NSString *)log {
    [self appendLog:log withLine:YES];
}

- (void)appendLog: (NSString *)log withLine:(BOOL)isAddLine {
    if ((nil == log) || (0 == log.length)) {
        return;
    }
    NSMutableString *text = [NSMutableString stringWithString:self.logTextView.text];
    [text appendString:log];
    if (isAddLine) {
        [text appendString:@"\n"];
    }
    self.logTextView.text = [text copy];
}

# pragma mark - c funtions
// 阶乘
int factorial(int n) {
    if (n > 100) {
        return -1; // 太大了，算不出来，会越界
    }
    if (n == 1 || n ==0 ) {
        return 1;
    }
    return n * factorial(n - 1);
}

// 最大公约数;辗转相除法；http://blog.csdn.net/iwm_next/article/details/7450424
int gcd(int a, int b) {
    
    int temp = 0;
    
    if (a < b) {
        
        temp = a;
        
        a = b;
        
        b = temp;
        
    }
    
    while (b != 0) {
        
        temp = a % b;
        
        a = b;
        
        b = temp;
        
    }
    
    return a;
}

// 快速排序；http://blog.csdn.net/morewindows/article/details/6684558
void quick_sort(int s[], int l, int r) {
    if (l < r) {
        //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
        int i = l, j = r, x = s[l];
        while (i < j) {
            while(i < j && s[j] >= x) {// 从右向左找第一个小于x的数
                j--;
            }
            if(i < j) {
                s[i] = s[j];
            }
            
            while(i < j && s[i] < x) {// 从左向右找第一个大于等于x的数
                i++;
            }
            if(i < j) {
                s[j] = s[i];
            }
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // 递归调用
        quick_sort(s, i + 1, r);
    }
}

// 冒泡排序；http://www.cnblogs.com/kkun/archive/2011/11/23/2260280.html
void bubble_sort(int s[], int length) {
    for (int i = 0; i < length; i++) {
        for (int j = i; j < length; j++) {
            if (s[i] > s[j]) {
                int temp = s[i];
                s[i] = s[j];
                s[j] = temp;
            }
        }
    }
}

// 二分查找；http://www.cnblogs.com/shuaiwhu/archive/2011/04/15/2065062.html
int binary_search(int* a, int len, int goal) {
    int low = 0;
    int high = len - 1;
    while (low <= high) {
        int middle = (high - low) / 2 + low; // 直接使用(high + low) / 2 可能导致溢出
        if (a[middle] == goal) {
            return middle;
        }
        //在左半边
        else if (a[middle] > goal) {
            high = middle - 1;
        }
        //在右半边
        else {
            low = middle + 1;
        }
    }
    //没找到
    return -1;
}

// 判断质数：http://blog.csdn.net/huang_miao_xin/article/details/51331710
int isPrime(int n) {
    for(int i = 2; i <= sqrt(n); i++) {
        if(n % i == 0) {
            return 0;
        }
    }
    return 1;
}

// 字符串逆序输出；http://www.cnblogs.com/graphics/archive/2011/03/09/1977717.html
void reverse(char s[]) {
    // p指向字符串头部
    char *p = s ;
    
    // q指向字符串尾部
    char *q = s ;
    while('\0' != *q) {
        q++ ;
    }
    q-- ;
    
    // 交换并移动指针，直到p和q交叉
    while(q > p) {
        char t = *p;
        char m = *q;
        *p = m;
        *q = t;
        p++;
        q--;
    }
}

@end
